package leetcode.editor.utils;

import java.util.*;

public class quickSort {

    private static final Random rng = new Random(System.currentTimeMillis());

    public void quickSort(int[] nums, int left, int right) {
        // 终止条件, left>=right
        if (left >= right) {
            return;
        }

        int pivotIndex = partition(nums, left, right);
        quickSort(nums, left, pivotIndex - 1);
        quickSort(nums, pivotIndex + 1, right);
    }

    /*
     * 不添加随机数在顺序和逆序数组上性能很差, 几乎是On^2.
     */
    private int partition(int[] nums, int left, int right) {
        int randomIndex = left + rng.nextInt(right - left + 1); // 左闭右开[0, r-l+1), 或者说是[0, r-l].
        swap(nums, left, randomIndex);
        int pivot = nums[left];
        int j = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] <= pivot) {
                j++;
                swap(nums, i, j);
            }
        }
        swap(nums, left, j);
        return j;
    }

    /* 
     * 二路快排
     */
    private int partition2Way(int[] nums, int left, int right) {
        int randomIndex = left + rng.nextInt(right - left + 1); // 左闭右开[0, r-l+1), 或者说是[0, r-l].
        swap(nums, left, randomIndex);
        int pivot = nums[left];
        int i = left + 1; // le  -> less equals
        int j = right;  // ge  -> greater equals
        // nums[left+1, i) < pivot
        // nums(j, right] > pivot
        while (i <= j) {
            while (i <= j && nums[i] <= pivot) {
                i++;
            }
            while (i <= j && nums[j] > pivot) {
                j--;
            }
            // le来到了大于pivot的位置
            // ge来到了小于等于pivot的位置
            if (i < j) {
                swap(nums, i, j);
            }
        }
        // or
        /* while (true){
            while (i <= j && nums[i] < pivot) i++;
            while (i <= j && nums[j] > pivot) j++;
            // le来到了大于等于pivot的位置
            // ge来到了小于等于pivot的位置
            if (i >= j) break;
            swap(nums, i, j);
            i++;
            j++;
        } */
        swap(nums, left, j);
        return j;
    }


    /* 
     * 三路快排
     */
    public void quickSort3Way(int[] nums, int left, int right) {
        // 终止条件, left>=right
        if (left >= right) {
            return;
        }

        int randomIndex = left + rng.nextInt(right - left + 1); // 左闭右开[0, r-l+1), 或者说是[0, r-l].
        swap(nums, left, randomIndex);
        int pivot = nums[left];
        int lt = left + 1; // lt  -> less than
        int gt = right;  // gt  -> greater than
        // nums[left+1, lt) < pivot
        // nums[lt, gt] = pivot
        // nums(gt, right] > pivot
        int i = left + 1;

        while (i <= gt) {
            if (nums[i] < pivot) {
                swap(nums, lt, i);
                lt++;
                i++;
            }
            if (nums[i] == pivot) {
                i++;
            }
            if (nums[i] > pivot) {
                swap(nums, i, gt);
                gt--;
                // 交换后的元素还要再次读一下, 所以不i++;
            }
        }
        // 交换切分元素
        swap(nums, left, lt - 1);

        quickSort(nums, left, lt - 1);
        quickSort(nums, gt + 1, right);
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}
